package jzoffer;

import java.util.HashMap;


/**
 * @author MaoLin Wang
 * @date 2020/10/10 3:53 下午
 */
public class _35复杂链表的复制 {
    public Node copyRandomList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        HashMap<Node, Node> hashMap = new HashMap<>();
        Node temp = head;
        while (temp != null) {
            hashMap.put(temp, new Node(temp.val));
            temp = temp.next;
        }
        temp = head;
        while (temp != null) {
            hashMap.get(temp).next = hashMap.get(temp.next);
            hashMap.get(temp).random = hashMap.get(temp.random);
            temp = temp.next;
        }
        return hashMap.get(head);
    }

    public Node copyRandomList2(Node head) {
        if (head==null){
            return null;
        }
        copy(head);
        randomHead(head);
      return   relink(head);
    }

    private Node relink(Node head) {

        Node res=head.next;
        while (head!=null){
            Node next=head.next.next;
            Node copy=head.next;
            head.next=next;
            copy.next=next==null?null:next.next;
            head=head.next;
        }
        return res;
    }

    private void randomHead(Node head) {
        while (head!=null){
            Node random = head.random;
            Node copy = head.next;
            if (random!=null){
               copy.random=random.next;
           }

            head=copy.next;
        }
    }

    private void copy(Node head) {
        while (head!=null){
            Node copy=new Node(head.val);
            Node next=head.next;
            head.next=copy;
            copy.next=next;
            head=copy.next;

        }
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
    }
}